package arithmetic.topk;


/**
 * 求最小的k个数
 * <p>
 * 分治法,类似快排的做法
 */
public class TopMinK {
    public static void main(String[] args) {
        int[] a = {2, 20, 3, 7, 9, 1, 17, 18, 0, 4};
        int k = 6;
        getTopKMinBySort(a, 0, a.length - 1, k);
        for (int i = 0; i < k; i++) {
            System.out.print(a[i] + " ");
        }
    }

    static void getTopKMinBySort(int[] a, int first, int end, int k) {
        if (first >= end) {
            return;
        }
        int partitionIndex = partition(a, first, end);

        if (partitionIndex == k - 1) {
            return;
        } else if (partitionIndex < k - 1) {
            getTopKMinBySort(a, partitionIndex + 1, end, k);
        } else {
            getTopKMinBySort(a, first, partitionIndex - 1, k);
        }
    }

    static int partition(int[] a, int first, int end) {
        int i = first;
        int index = a[end]; // 随便找一个数，分成两部分，一部分大于这个数，一部分小于这个数
        for (int j = first; j < end; j++) {
            if (a[j] < index) {
                int temp = a[j];
                a[j] = a[i];
                a[i] = temp;
                i++;
            }
        }
        a[end] = a[i];
        a[i] = index;
        return i;
    }
}